#include <bits/stdc++.h>
using namespace std;

// 【题目】2454. 下一个更大元素 IV
// 【难度】困难
// 【提交】2025.9.25 https://leetcode.cn/problems/next-greater-element-iv/submissions/666034482
// 【标签】单调栈
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> stk1, stk2;
        
        for (int i = 0; i < n; i++) {
            int current = nums[i];
            
            while (!stk2.empty() && nums[stk2.top()] < current) {
                ans[stk2.top()] = current;
                stk2.pop();
            }
            
            stack<int> temp;
            while (!stk1.empty() && nums[stk1.top()] < current) {
                temp.push(stk1.top());
                stk1.pop();
            }
            
            while (!temp.empty()) {
                stk2.push(temp.top());
                temp.pop();
            }
            
            stk1.push(i);
        }
        
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 学到了to_string(), stol(), next_permutation()的用法，还学到了三元运算符return (A) && (B) ? C : D;
*/


/*
--------------------------------------------------------------------------------------------------------------
（（学习笔记：LeetCode 2454「下一个更大元素 IV」）​​

​​（提交记录：C++，用时  ms，内存  MB）​​

一、题意与模型
给定一个非负整数数组 nums，对于每个元素 nums[i]，需要找到其第二大整数，即满足：
j > i且 nums[j] > nums[i]
在 i和 j之间恰好存在一个 k满足 nums[k] > nums[i]
如果不存在这样的 nums[j]，则返回 -1

二、算法思路
使用双单调栈技术：
​stk1​：存储尚未找到第一个更大元素的索引（主栈）
​stk2​：存储已经找到第一个更大元素，正在等待第二个更大元素的索引（候补栈）
​temp​：临时栈，用于辅助元素转移

三、你的实现思路
cpp
下载
复制
运行
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> stk1, stk2;
        
        for (int i = 0; i < n; i++) {
            int current = nums[i];
            
            // 处理stk2：当前元素可能是stk2中元素的第二个更大元素
            while (!stk2.empty() && nums[stk2.top()] < current) {
                ans[stk2.top()] = current;
                stk2.pop();
            }
            
            // 处理stk1：找到当前元素的第一个更大元素
            stack<int> temp;
            while (!stk1.empty() && nums[stk1.top()] < current) {
                temp.push(stk1.top());
                stk1.pop();
            }
            
            // 将找到第一个更大元素的元素转移到stk2
            while (!temp.empty()) {
                stk2.push(temp.top());
                temp.pop();
            }
            
            stk1.push(i);
        }
        
        return ans;
    }
};
四、逐行注释（带细节提醒）
cpp
下载
复制
运行
class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);        // 初始化答案数组，默认值为-1
        stack<int> stk1, stk2;         // 双栈：stk1主栈，stk2候补栈
        
        for (int i = 0; i < n; i++) {  // 从左向右遍历数组
            int current = nums[i];      // 当前元素值
            
            // 1. 处理stk2中的元素：当前元素可能是它们的第二个更大元素
            while (!stk2.empty() && nums[stk2.top()] < current) {
                ans[stk2.top()] = current;  // 找到第二个更大元素，设置答案
                stk2.pop();                 // 该元素处理完成，弹出栈
            }
            
            // 2. 处理stk1中的元素：当前元素可能是它们的第一个更大元素
            stack<int> temp;                // 临时栈用于暂存
            while (!stk1.empty() && nums[stk1.top()] < current) {
                temp.push(stk1.top());      // 将找到第一个更大元素的元素暂存
                stk1.pop();                 // 从主栈弹出
            }
            
            // 3. 将暂存的元素转移到stk2，等待第二个更大元素
            while (!temp.empty()) {
                stk2.push(temp.top());      // 转移到候补栈
                temp.pop();                 // 清空临时栈
            }
            
            stk1.push(i);                  // 将当前索引入主栈
        }
        
        return ans;
    }
};
五、正确性证明
​单调性维护​：两个栈都保持单调递减特性，确保能正确找到更大元素
​元素流动​：stk1→ temp→ stk2的流动过程准确反映了"找到第一个更大元素"的状态转换
​时机把握​：在当前元素处理完可能的第二个更大元素后，再处理第一个更大元素，最后压入自身，逻辑顺序正确

六、复杂度分析
​时间​：O(n)，每个元素最多被压入和弹出每个栈各一次
​空间​：O(n)，最坏情况下需要存储所有元素的索引

七、优缺点分析
​优点：​​
时间复杂度最优，线性时间解决复杂问题
思路清晰，双栈分工明确
代码结构整齐，易于理解和维护

​缺点：​​
使用了临时栈 temp，增加了一定的空间复杂度
算法思路相对复杂，需要理解状态转换
使用了三个栈操作，常数因子较大

八、改进建议
​使用vector代替stack​：可以用 vector模拟栈，避免频繁的栈操作开销
​优化临时栈​：可以尝试直接操作，避免使用临时栈
​使用索引操作​：对于 stk1的处理可以直接使用索引而非临时栈

九、一句话总结
该算法通过巧妙的双单调栈设计，使用 stk1和 stk2分别处理"第一个更大元素"和"第二个更大元素"的查找，以 O(n) 时间复杂度和 O(n) 空间复杂度高效解决了寻找第二大整数的问题，体现了栈在处理序列关系问题中的强大能力。
--------------------------------------------------------------------------------------------------------------
*/